<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        解题思路：
        - f(k) = 从前 k 个房屋中能偷窃到的最大数额
        - Ak = 第 k 个房屋的钱数
        - f(k) = max( f(k-2)) + Ak, f(k-1) )

        解题步骤：
        - 定义子问题：f(k) = max(f(k-2) + Ak, f(k-1))
        - 反复执行：从 2 循环到 n, 执行上述公式
     -->
</head>
<body>
    <script>
        var rob = function(nums) {
            if (nums.length === 0) {return 0;} // 如果没有房屋，则返回0
            const dp = [0, nums[0]]; // dp[i] 为前i个房屋能打劫到的最大金额，因为保存了第0个房屋最大能抢到0元。所以dp数组比nums数组要多一位
            for (let i = 2; i<=nums.length; i++) {
                // 前i个能抢到的最大值是：前i-2个房屋能抢到金额最大值加上当前房屋金额，或者前i-1个房屋能抢到的金额最大值
                dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]); 
            }
            return dp[dp.length-1];
        };

        // 优化空间复杂度，不使用数组
        var rob = function(nums) {
            if (nums.length === 0) {return 0;}
            let dp0 = 0;
            let dp1 = nums[0];
            for (let i = 2; i<=nums.length; i++) {
                const dp2 = Math.max(dp0 + nums[i-1], dp1);
                dp0 = dp1;
                dp1 = dp2;
            }
            return dp1;
        };
    </script>
</body>
</html>